#include <iostream>
#include <ctime>

const int maxsize = 100;
using namespace  std;
int a[maxsize];
int n;
void print(int a[])
{
    for(int i=1;i<=n;++i)
    {
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
//创建大根堆 效率o(n)
void createBigHeap(int a[],int n)
{
    for(int i=n/2;i>=1;--i)
    {

        for(int j=2*i;j<=n;j*=2)
        {

            //j始终指向左右孩子这种最大的那一个  如果发生交换i需要更新为新的孩子
            //如果右孩子存在并且有害
            if(j+1<n&&a[j+1]>a[j])
            {
                j=j+1;
            }
            //大根堆 如果孩子大就和父亲交换
            if(a[i]<a[j])
            {
                swap(a[i],a[j]);
                i=j;
            } else{
                break;
            }


        }
    }
}
void AdjustHeap(int i,int n)
{
    //从i这个位置开始调整元素
    for(int k=2*i;k<=n;k*=2)
    {
        if(k+1<n&&a[k+1]>a[k])
        {
            k++;
        }
        if(a[i]<a[k])
        {
            swap(a[i],a[k]);
            i=k;
        } else
        {
            break;
        }
    }

}
void HeapSort(int a[],int n)
{
    //从最后一个元素开始和第一个元素交换 交换之后再次调整大根堆
     for(int i=n;i>=2;--i)
     {

         swap(a[i],a[1]);
         AdjustHeap(1,i-1);

     }
}
int main() {
    //初始化数组
    cin>>n;
    srand(time(0));
    for(int i=1;i<=n;++i)
    {
        a[i]=rand()%100;
    }
    print(a);
    //下面从1开始
    createBigHeap(a,n);

    HeapSort(a,n);



    print(a);



    return 0;
}
